//
//  XBStringMatch.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/19.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBStringMatch.h"
#include <string.h>

/**
 *  
 
 普通的串的匹配算法：
 
 这种串的匹配算法效率比较低，最好的情况下是一次匹配就完事。否则就是其他情况
 
 A：每次字串的第一个字母和原始串的第一个字母都不相等，这样后面的就不用匹配了，原始串i就可以增加，一直到最后i = 原始串长度- 字串长度-1.匹配到、
 
 这个时候和上来就匹配到概率是相等的。都没有因为字串和原始串前面有部分相同的内容进行了匹配。凡是字串和原始串匹配的部分都不是浪费时间的。
 
 最好的情况下时间复杂度是O(1),最坏的是O(N+M)N是原始串长度，M是字串的长度
 
 
 B：这就是其他情况了。在i增加的过程中，字串和原始串进行了对比，但是没有成功，然后i又开始增加了。
 最坏的情况是匹配到字串的长度的最后一位才发现不匹配，而且这样的情况在i<原始串长度-字串长度-1之前一直发生。。
 
 这个时候时间复杂度就是O(M*(N-M)+M)
 
 
 
 
    返回一个字符串在原始字符串的索引，不存在返回-1
 *
 *  @param originS  原始字符串
 *  @param subSting 字串
 *
 *  @return 字串在原始串的位置
 */

int indexOfSubString(char * originS,char * subSting)
{
    
    unsigned long  lenOriginS = strlen(originS);
    unsigned long  lenSubStr = strlen(subSting);
    if (lenSubStr>lenOriginS) {
        return -1;
    }
    //最外的循环控制字串的比较次数
    for (int i = 0; i<lenOriginS-lenSubStr; i++) {
        
        int equalCount =0;
        //这层循环用来做字串和原始串里面的字串比较
        for (int j=0; j<lenSubStr; j++) {
            if (subSting[j]==originS[i+j]) {
                
                equalCount++;
            }
            else
            {
                break;
            }
        }
        if (equalCount==lenSubStr) { //这里说明匹配到了
            
            return i;
        }
    }
    return -1;
}

void testStringMatch()
{
    
    char * s1 = "abcda";
    char * s2 = "ab";
    printf("字串的索引是%d\n",indexOfSubString(s1, s2));

}

/**
 *  KMP匹配模式算法：(下面内容来自大话数据结构书籍)
 
    普通情况下字符串匹配过程
 
A:  字串中每个字符都不相等的情况。
    ** abcdefgab    1
    -- abcdex
 
    ** abcdefgab    2
    --  abcdex

    ** abcdefgab    3
    --   abcdex
 
    ** abcdefgab    4
    --    abcdex
 
    ** abcdefgab    5
    --     abcdex
 
    ** abcdefgab    6
    --      abcdex
 
    其实 2345步骤判断是多余的。因为：字串abcdex首字母a和后面的字母都不相同。第一次匹配的时候原始串和字串匹配到第5位才开始不相等的。
    所以字串中的第一个字符a，不可能和原始串中前5位有相等的可能。所以2345就可以直接省略了。直接从6开始。因为第六位不相等，所以不清楚字串的
    第一位和原始串的第六位是否相等，所以步骤6不可省略
 
 B：字串中有些字符相等。i和j分别表示原始串和字串的索引
 
    ** abcabca    (1)    i=6
    -- abcabx    j=6
    
    ** abcabca    (2)    i=2
    --  abcabx           j=1
    
    ** abcabca    (3)    i=3
    --   abcabx          j=1
 
    // --- 2 3 步骤可以省略
    
    ** abcabca    (4)    i=4
    --    abcabx         j=1   对比字串的a
    
    ** abcabca    (5)    i=5
    --    abcabx         j=2   对比字串的b
    
    //---- 4 5 也可以省略，因为abcabx中有重复的了，在前面已经比较过了，所以不需要再次比较了，
 
    ** abcabca    (6)    i=6
    --    abcabx         j=3   对比字串的c
    
 通过上面两个例子来看，这里的i匹配过程中始终没有变小，j的值变化和原始串没有太大关系，主要是和自身结构中重复程度相关
 把T串中的各个位置的j值的变化定义为一个数组next，next的长度就是T的长度。
    
 A：j=1.next[j]=0
 B:当存在重复字串 Max{K|1<K<j,重复的字串符合 P(1)..P(K-1) = P(j-k+1)...P(j-1) next[j]=
 C:其他情况
 
 
 next[j]数值的推导
 T = 'abcdex'
 j=1,next[1]=0;
 j=2,j由1到j-1只有一个字符'a',属于其他情况next[2]=1;
 j=3,j由1到j-1的串是ab，a和b不相等所以，next[3]=1;
 所以next[j]=011111
 
 
 T='abcabx'
 带入公式计算得到结果
 j=1  next[j]=0
 j=2  next[j]=1
 j=3  next[j]=1
 j=4  next[j]=2
 j=5  next[j]=3
 
 T="ababaaaba"//这是自己练习验证
 next = "011234223"
 
*/

//计算next的
void get_next(char * str,int * next)
{
    int i,j;
    i = 1;
    j=0;
    next[1]=0;
    while (i<strlen(str)) {
        
        if (j==0||str[i]==str[j])//str[i]表示后缀单个字符，str[j]表示前缀单个字符
        {
            i++;
            j++;
            next[i]=j;
        }
        else
        {
            j = next[j];
        }
    }
    
}

void testGetNext()
{
    int a[100];
    get_next("ababaaaba", a);
    for (int i =0; i<9; i++) {
        
        printf("%d",a[i]);
    }
}



























